Application Ser. No. 09/532,411, titled xe2x80x9cShared Cache Wordline Decoder For Redundant and Regular Addresses,xe2x80x9d filed Mar. 22, 2000, pending. Application Ser. No. 09/887,870, titled xe2x80x9cTag Design For Cache Access With Redundant Form Address,xe2x80x9d filed Jun. 22, 2001, pending.
This invention relates generally to decoders for memory, and in particular to decoders for high-speed cache memory.
A cache is a fast memory for storing copies of frequently accessed data. As processors become faster, cache access time is often a dominating factor in system performance. Conflicting goals face designers of cache memory systems. Smaller caches provide faster access times, but larger caches provide higher hit ratios thereby reducing penalties associated with accessing slower memory.
Two prior art methods are shown in U. S. Pat. No. 5,555,529. One typical prior art cache is shown in FIG. 1. A wordline decoder 30 receives an address to access memory array 32. Depending on the address, exactly one wordline, 60, 61, 62, 63, 64, or 65 is activated. For example, if wordline 60 is activated, then memory locations 50, 80, 85, and 90 will be accessed. When these memory locations are accessed, two bits of information at each memory location, 50, 80, 85, and 90 will be presented on a pair of bitlines, 35, 39, 41, and 45 to column multiplexers (MUXs) 99, 101, 103, and 105. This technique is known as column multiplexing. One bit from each pair will be selected by a column selector to be presented to the sense amplifiers 100, 102, 104, and 106. It should be noted that columns typically supply both true and complemented signal values for each bit stored at a memory location. Other column multiplexing schemes are in ratios of 4:1, 8:1 and 16:1, with 2:1 and 4:1 being most common. Advantages associated with column multiplexing include better area usage since memory read circuits and write circuits can be laid out using a wider pitch, and more room is provided for global routing over memory cells. Disadvantages include higher power usage and slower multiplexers for higher column multiplexing ratios.
A second prior art method is shown in FIG. 2. In this case, wordline decoder 125 activates either wordlines associated with array 120 or wordlines associated with array 122, but not both. If for example, wordline 130 is activated then bitline pairs 135, 137, 139 and 140 each supply one bit of information comprising both true and complemented signals to sense amplifiers 148, 144, 142, and 145. On the other hand, if wordline 150 is activated then bitline pairs 152, 155, 158 and 160 each supply one bit of information comprising both true and complemented signals to sense amplifiers 162, 164, 166, and 168. One advantage of this technique is that there is a power savings through discharging only the needed memory locations. Disadvantages include forcing a narrower pitch and greater probability of masked soft errors going undetected.
Another disadvantage with both of these prior methods involves computing large addresses. Since a current trend in processor design is to devote a substantial proportion of chip area to cache memory, much effort has been invested in improving access times for large caches. But for large addresses, the time it takes an adder to propagate a carry signal in computing the address is a significant factor.
In one prior art method, Cortadella et al [xe2x80x9cEvaluation of A+B=K Conditions Without Carry Propagation,xe2x80x9d IEEE Transactions on Computers, vol. 41, pp. 1484-1488, November, 1992] show that an equality test does not require carry propagation. One representation of a sum A+B, which is suitable for use in a carry nonpropagative equality test, is known as half-adder or carry-sum form. The carry-sum representation uses a carry bit, Ci, and a sum bit, Si, to represent a binary digit of a number in the ith digit position. In carry-sum form each number may have multiple valid representations. In a system of numbers, where each number is assigned multiple binary representations, the numbers are said to be in redundant form.
The carry-sum redundant form representation permits numbers to be added together while eliminating the need to propagate carry signals along the length of the address.
Another example, of a redundant form is called sign-digit. Each binary digit is represented as a sign bit, Xsi, and a magnitude bit, Xmi, and can take on values of 1, 0, and xe2x88x921.
Addresses can be calculated in carry-save or sign-digit redundant forms faster than through traditional adders, and wordline comparisons can be performed to access data without requiring carry propagation. Yet, techniques for cache column multiplexing based on specific address-bit values must be computed from redundant representations that are not unique. Therefore, computing column selectors may become a critical path in accessing cache.